package java_0217;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 单调栈解决下一个更大元素问题
 */
public class Num496_NextGreatNum {
    //单调栈
    private Stack<Integer> stack=new Stack<>();
    //存储nums2中每个元素（key）以及它的下一个更大元素值(value)
    private Map<Integer,Integer> map=new HashMap<>();
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //1.扫描nums2,维护单调栈，找到nums2的每个元素的下一个更大元素值
        //倒着向前遍历：为了正着解决问题（向后寻找第一大元素）
        for (int i = nums2.length-1; i >= 0; i--) {
            //当栈不为空且栈顶元素<=当前元素
            while(!stack.isEmpty()&&stack.peek()<=nums2[i]){
                //持续出栈
                stack.pop();
            }
            //找到下一个更大元素
            int nextGreatValue=stack.isEmpty()?-1:stack.peek();
            //处理完毕后，当前元素压入栈中：因为当前元素可能是下一个元素的更大元素
            stack.push(nums2[i]);
            map.put(nums2[i],nextGreatValue );
        }
        //再次扫描nums1,取出每个元素对应的value值就是结果集
        int[] ret=new int[nums1.length];
        for (int i = 0; i < ret.length; i++) {
            //取得每个nums1中的元素对应的value值
            // map.get():根据指定key取得value
            ret[i]=map.get(nums1[i]);
        }
        return ret;
    }
}
